package com.tgy.algorithm._经典题目01;

import com.tgy.algorithm.base.other.BiTreeNode;

import java.util.Stack;

/**
 * https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/description/
 *
 * 将一个 二叉搜索树 就地转化为一个 已排序的双向循环链表 。
 *
 * 对于双向循环列表，你可以将左右孩子指针作为双向循环链表的前驱和后继指针，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
 *
 * 特别地，我们希望可以 就地 完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中最小元素的指针。
 */
public class _022_将二叉搜索树转化为排序的双向链表 {

    static class Info {
        // 头
        BiTreeNode head;
        // 尾
        BiTreeNode tail;

        Info(BiTreeNode head,BiTreeNode tail) {
            this.head = head;
            this.tail = tail;
        }
    }

    public static BiTreeNode generalBiTreeNode() {

        /**
         *               9
         *           6        12
         *        3     7  10     13
         */
        BiTreeNode root = new BiTreeNode(9);
        root.left = new BiTreeNode(6);
        root.right = new BiTreeNode(12);
        root.left.left = new BiTreeNode(3);
        root.left.right = new BiTreeNode(7);
        root.right.left = new BiTreeNode(10);
        root.right.right = new BiTreeNode(13);
        return root;
    }

    public static BiTreeNode sbt2BiLinked(BiTreeNode sbt) {

        Stack<BiTreeNode> stack = new Stack<>();
        BiTreeNode node = sbt;
        BiTreeNode firstNode = null;

        BiTreeNode preNode = null;
        while (!stack.isEmpty() || node != null) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            }else {
                node = stack.pop();
                if (preNode != null) {
                    node.left = preNode;
                    preNode.right = node;
                }else {
                    firstNode = node;
                }

                preNode = node;
                node = node.right;
            }
        }

        firstNode.left = preNode;
        preNode.right = firstNode;

        return firstNode;
    }


    public static BiTreeNode sbt2BiLinked01(BiTreeNode root) {

        if (root == null) {
            return null;
        }

        return doSbt2BiLinked01(root).head;
    }


    public static Info doSbt2BiLinked01(BiTreeNode root) {

        if (root == null) {
            return null;
        }

        Info leftInfo = doSbt2BiLinked01(root.left);
        Info rightInfo = doSbt2BiLinked01(root.right);

        BiTreeNode head = null;
        BiTreeNode tail = null;

        if (leftInfo != null) {
            head = leftInfo.head;
            leftInfo.tail.right = root;
            root.left = leftInfo.tail;
        }else {
            head = root;
        }

        if (rightInfo != null) {
            tail = rightInfo.tail;
            rightInfo.head.left = root;
            root.right = rightInfo.head;
        }else {
            tail = root;
        }


        if (head != tail) {
            head.left = tail;
            tail.right = head;
        }

        return new Info(head,tail);
    }

    public static void main(String[] args) {

        BiTreeNode root = generalBiTreeNode();
//        BiTreeNode biTreeNodeRoot = sbt2BiLinked(root);
//        System.out.println(biTreeNodeRoot);
        BiTreeNode biTreeNode = sbt2BiLinked01(root);
        BiTreeNode node = biTreeNode;
        while (true) {
            System.out.println(node.value);
            node = node.right;
            if (node == biTreeNode) {
                break;
            }
        }
        System.out.println(biTreeNode);
    }
}
